// class Solution {
// public:
//     int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
//         int size = gas.size();
//         auto add = gas;
//         for(int i = 0; i < size; i++) add[i] -= cost[i];
//         int sum = 0;
//         for(auto e : add) sum += e;
//         if(sum < 0) return -1;
//         for(int i = 0; i < size;)
//         {
//             // cout << i << ' ';
//             int cur = 0;
//             int j = i;
//             do {
//                 cur += add[j];
//                 if(cur < 0) break;
//                 j = (j + 1) % size;
//             } while(j != i);
//             if(cur >= 0 && i == j) return i;
//             // cout << cur << ' ' << j << endl;
//             i = j + 1;
//         }
//         // for(auto e : add) cout << e << ' '; cout << endl;

//         return 0;
//     }
// };
// // -2 -2 -2  3  3

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int size = gas.size();
        vector<int> diff(size);
        for (int i = 0; i < size; i++)
            diff[i] = gas[i] - cost[i];
        for (int i = 0; i < size; )
        {
            int j = (i + 1) % size;
            int cur = diff[i];
            while (cur >= 0 && j != i)
            {
                cur += diff[j];
                j = (j + 1) % size;
            }
            if (cur >= 0) return i;
            if (j <= i) return -1;
            i = j;
        }
        return -1;
    }
};